package STO_10_1;

import java.util.Arrays;

public class Solution {
	public int fib(int n) {
		if (n == 0 || n == 1) {
			return n;
		}
		int first = 0;
		int second = 1;
		for (int i = 0; i < n; i++) {
			first = first + second;
			second = first - second;
			first %= 1000000007;
		}
		return first;

	}
	public int fib_DP(int n) {
		if (n == 0 || n == 1) {
			return n;
		}
		int[] dp = new int[n+1];
		dp[1]=1;
		dp[0]=0;
		for (int i = 2; i <= n; i++) {
			dp[i]=(dp[i-1]+dp[i-2])%1000000007;
		}
		System.out.println(Arrays.toString(dp));
		return dp[n];

	}
}
